#include <iostream>
#include <vector>
using namespace std;


int max_value_recur(vector<vector<vector<int>>> &group, int g, int w)
{
        if(g == 0){
                return 0;
        }

        int max_value = max_value_recur(group, g - 1, w);
        for(int i = 0; i < group[g].size(); i++){
                if(group[g][i][0] <= w){
                        max_value = max(max_value, max_value_recur(group, g - 1, w - group[g][i][0]) + group[g][i][1]);
                }
        }
        return max_value;
}

int max_value_dp(vector<vector<vector<int>>> &group, int w)
{
        int n = group.size();
        vector<vector<int>> dp(n + 1, vector<int>(w + 1, 0));
        for(int i = 1; i<=n; i++){
                int g = i - 1;
                for(int j = 1; j<=w; j++){
                        dp[i][j] = dp[i - 1][j];
                        for(int k = 0; k < group[g].size(); k++){
                                if(group[g][k][0] <= j){
                                        dp[i][j] = max(dp[i][j], dp[i - 1][j - group[g][k][0]] + group[g][k][1]);
                                }
                        }
                }
        }
        return dp.back().back();
}

int max_value_dp_sp(vector<vector<vector<int>>> &group, int w)
{
        int n = group.size();
        vector<int> dp(w + 1, 0);
        for(int i = 1; i <= n; i++){
                int g = i - 1;
                for(int j = w; j > 0; j--){
                        for(int k = 0; k < group[g].size(); k++){
                                if(group[g][k][0] <= j){
                                        dp[j] = max(dp[j], dp[j - group[g][k][0]] + group[g][k][1]);
                                }
                        }
                }
        }
        return dp.back();
}

int main()
{
        int v, n, t;
        cin>>v>>n>>t;

        vector<vector<vector<int>>> group(t + 1);
        for(int i = 1; i <= n; i++){
                int w, c, p;
                cin>>w>>c>>p;
                group[p].push_back({w, c});
        }
        //cout<<max_value_recur(group, t, v)<<endl;
        cout<<max_value_dp_sp(group, v)<<endl;
        return 0;
}
